{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 决策树要经历的两个阶段\n",
    "\n",
    "## 1. 构造\n",
    "\n",
    "构造的过程就是选择什么属性作为节点的过程， 那么在构造的过程中，会粗壮乃三种节点\n",
    "1. 根节点： 就是树的最顶端， 最开始的那个节点\n",
    "2. 内部节点： 就是树中间的哪些节点\n",
    "3. 叶节点： 就是树的最底部的节点，也就是决策结果\n",
    "\n",
    "节点之间存在父子关系， 比如根节点会有子节点， 子节点会有子子节点， 但是到了叶子节点就停止了， 叶子节点不存在子节点， 那么在构造的过程中，你要解决三个问题\n",
    "- 选择哪个属性作为根节点\n",
    "- 选择哪些属性作为子节点\n",
    "- 什么时候停止并得到目标状态， 即叶子节点\n",
    "\n",
    "## 2. 剪枝\n",
    "\n",
    "不需要太多的判断， 同样可以得到不错的结果， 之所以这么做， 是为了防止`过拟合（overfitting)`现象的发生\n",
    "\n",
    "在对决策树构造的过程中， 一般可以分为“预剪枝”（Pre-Prunning)和“后剪枝”（Post-Prunning)\n",
    "\n",
    "- 预剪枝是在决策树构造时就进行剪枝。方法是在构造的过程中对节点进行评估，如果对某个节点进行划分，在验证集中不能带来准确性的提升，那么对这个节点进行划分就没有意义，这时就会把当前节点作为叶节点，不对其进行划分\n",
    "\n",
    "- 后剪枝就是在生成决策树之后再进行剪枝，通常会从决策树的叶节点开始，逐层向上对每个节点进行评估。如果剪掉这个节点子树，与保留该节点子树在分类准确性上差别不大，或者剪掉该节点子树，能在验证集中带来准确性的提升，那么就可以把该节点子树进行剪枝。方法是：用这个节点子树的叶子节点来替代该节点，类标记为这个节点子树中最频繁的那个类"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 信息熵（entropy) - 信息的不确定度\n",
    "\n",
    "在信息论中， 随机离散事件出现的概率存在这不确定性， 为了衡量这种信息的不确定性， 信息学之父引入了信息熵的概念， 并给除了信息熵的数学公式\n",
    "\n",
    " $$Entropy(t)=-\\sum_{i=0}^{c-1}{p(i \\mid t)log_2 p(i \\mid t)}$$\n",
    " $p(i\\mid t)$ 代表了节点t为分类i的概率\n",
    "  \n",
    " 基本的总结的规律就是： 信息熵越大， 纯度越低。当集合中的所欲的样本均匀混合的时候， 信息熵最大， 纯度最低\n",
    "\n",
    "\n",
    " 在构造决策树的时候， 会基于纯度来构建， 而经典的“不纯度”的指标有三种\n",
    " \n",
    " * 信息增益（ID3算法）\n",
    " * 信息增益率（C4.5算法）\n",
    " * 基尼指数 （Cart算法)\n",
    " \n",
    " \n",
    " ### 1. ID3算法\n",
    "  计算的是信息增益，信息增益指的就是划分可以带来纯度的提高，信息熵的下降。它的计算公式，是父亲节点的信息熵减去所有子节点的信息熵。在计算的过程中，我们会计算每个子节点的归一化信息熵，即按照每个子节点在父节点中出现的概率，来计算这些子节点的信息熵。所以信息增益的公式可以表示为：\n",
    "  \n",
    " $$ Gain(D,a)=Entropy(D)-\\sum_{i=1}^{k}{\\frac{|D_i|}{|D|}Entropy(D_i)}$$\n",
    " \n",
    " 公式中 D是父亲节点， $D_i$是子节点， Gain(D,a)中的a作为D节点的属性选择"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: Tree Pages: 1 -->\r\n",
       "<svg width=\"208pt\" height=\"165pt\"\r\n",
       " viewBox=\"0.00 0.00 208.00 165.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 161)\">\r\n",
       "<title>Tree</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-161 204,-161 204,4 -4,4\"/>\r\n",
       "<!-- 0 -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>0</title>\r\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"145,-157 54,-157 54,-89 145,-89 145,-157\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"99.5\" y=\"-141.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">X[0] &lt;= 0.5</text>\r\n",
       "<text text-anchor=\"middle\" x=\"99.5\" y=\"-126.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">gini = 0.5</text>\r\n",
       "<text text-anchor=\"middle\" x=\"99.5\" y=\"-111.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">samples = 4</text>\r\n",
       "<text text-anchor=\"middle\" x=\"99.5\" y=\"-96.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">value = [2, 2]</text>\r\n",
       "</g>\r\n",
       "<!-- 1 -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>1</title>\r\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"91,-53 0,-53 0,-0 91,-0 91,-53\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-37.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-22.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">samples = 2</text>\r\n",
       "<text text-anchor=\"middle\" x=\"45.5\" y=\"-7.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">value = [2, 0]</text>\r\n",
       "</g>\r\n",
       "<!-- 0&#45;&gt;1 -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>0&#45;&gt;1</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M80.6134,-88.9485C75.6474,-80.2579 70.2776,-70.8608 65.2667,-62.0917\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"68.207,-60.1826 60.2067,-53.2367 62.1293,-63.6557 68.207,-60.1826\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"53.6288\" y=\"-73.6558\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">True</text>\r\n",
       "</g>\r\n",
       "<!-- 2 -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>2</title>\r\n",
       "<polygon fill=\"none\" stroke=\"black\" points=\"200,-53 109,-53 109,-0 200,-0 200,-53\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"154.5\" y=\"-37.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"middle\" x=\"154.5\" y=\"-22.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">samples = 2</text>\r\n",
       "<text text-anchor=\"middle\" x=\"154.5\" y=\"-7.8\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">value = [0, 2]</text>\r\n",
       "</g>\r\n",
       "<!-- 0&#45;&gt;2 -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>0&#45;&gt;2</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M118.736,-88.9485C123.794,-80.2579 129.264,-70.8608 134.367,-62.0917\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"137.516,-63.6401 139.521,-53.2367 131.466,-60.1189 137.516,-63.6401\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"145.907\" y=\"-73.7073\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">False</text>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x17c10f2c648>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from sklearn import tree\n",
    "import sys\n",
    "import os\n",
    "import graphviz\n",
    "import numpy as np\n",
    "os.environ[\"PATH\"] += os.pathsep + 'D:/Apps/Anaconda3/Library/bin/graphviz'\n",
    "# 创建数据 [ 红，大 ] ， 1== 是， 0== 否\n",
    "data = np.array([[1,1],[1,0],[0,1],[0,0]])\n",
    "# 数据标注为， 1== 好苹果， 0== 坏苹果\n",
    "target = np.array([1,1,0,0])\n",
    "clf = tree.DecisionTreeClassifier() # 创建决策树分类器模型\n",
    "clf = clf.fit(data, target) # 拟合数据\n",
    "# 最后利用 graphviz 库打印出决策树图\n",
    "dot_data = tree.export_graphviz(clf,out_file=None)\n",
    "graph = graphviz.Source(dot_data)\n",
    "graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 总结\n",
    "\n",
    "决策树是一种比较有用的商业智能分析法，对于既定的数据，可以给\n",
    "- 公司的决策层一个合理的决策方法\n",
    "- 当然也可用在智能客服的对话应用上面"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
